/*
 * @lc app=leetcode id=450 lang=cpp
 *
 * [450] Delete Node in a BST
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode *parent = nullptr;
         auto target = SearchNode(root, &parent, key);
         if (target == nullptr) {
             return root;
         }
         if (target->right) {
             TreeNode *q = target;
             TreeNode *p = target->right;
             while (p->left != nullptr) {
                 q = p;
                 p = p->left;
            }
            target->val = p->val;
            TreeNode *t = nullptr;
            if (p->right) {
                 t = p->right;
            } 
            if (q->left == p) {
                q->left = t;
            } else {
                q->right = t;
            }          
         } else if(target->left){
             TreeNode *q = target;
             TreeNode *p = target->left;
             while (p->right != nullptr) {
                 q = p;
                 p = p->right;
            }
            target->val = p->val;
            TreeNode *t = nullptr;
            if (p->left) {
                 t = p->left;
            } 
            if (q->left == p) {
                q->left = t;
            } else {
                q->right = t;
            }      
         } else {
             if (target == root) {
                 return nullptr;
             } else {
                if (parent->left == target) {
                    parent->left = nullptr;
                } else if (parent->right == target) {
                    parent->right = nullptr;
                }   
             }
         }   
         return root;         
    }
    TreeNode *SearchNode(TreeNode *root, TreeNode **parent, int key){
        if (root != nullptr) {
            if (root->val == key) {
                return root;
            } else if (key > root->val) {
                *parent = root;
                return SearchNode(root->right, parent, key);
            } else {
                *parent = root;
                return SearchNode(root->left, parent, key);
            }                
        } else {
            return nullptr;
        }   
    }


    
};
// @lc code=end

